//https://leetcode.cn/problems/maximum-number-of-operations-with-the-same-score-ii/
class Solution {
private:
	int func(int i, int j, int target, vector<int>& nums) {
		int n = nums.size();
		vector<vector<int>> vec(n, vector<int>(n, -1));
		return dfs(i, j, target, vec, nums);
	}

	int dfs(int i, int j, int target, vector<vector<int>>& vec, vector<int>& nums) {
		if (i >= j) {
			return 0;
		}
		int ans = 0;
		if (vec[i][j] != -1) {
			return vec[i][j];
		}
		if (nums[i] + nums[i + 1] == target) {
			// front 2
			ans = max(ans, dfs(i + 2, j, target, vec, nums) + 1);
		}
		if (nums[i] + nums[j] == target) {
			// front + back
			ans = max(ans, dfs(i + 1, j - 1, target, vec, nums) + 1);
		}
		if (nums[j] + nums[j - 1] == target) {
			// back 2
			ans = max(ans, dfs(i, j - 2, target, vec, nums) + 1);
		}
		vec[i][j] = ans;
		return ans;
	}
public:
	int maxOperations(vector<int>& nums) {
		int ans = 0;
		int n = nums.size();
		ans = max(ans, func(0, n - 1, nums[0] + nums[1], nums));
		ans = max(ans, func(0, n - 1, nums[0] + nums[n - 1], nums));
		ans = max(ans, func(0, n - 1, nums[n - 1] + nums[n - 2], nums));
		return ans;
	}
};
